package main

import "container/list"

type NestedInteger struct {
	t    bool
	i    int
	list []*NestedInteger
}

func (n NestedInteger) IsInteger() bool           { return n.t }
func (n NestedInteger) GetInteger() int           { return n.i }
func (n NestedInteger) GetList() []*NestedInteger { return n.list }

/*
NestedIterator 扁平化嵌套列表迭代器
*/
type NestedIterator struct {
	depthList *list.List // 遍历深度指针
}

/*
nestedElement 为 NestedIterator.depthList 的内置元素
*/
type nestedElement struct {
	nestedList []*NestedInteger // 元素
	index      int              // 当前遍历到的下标
}

/*
Constructor 构造器

NestedInteger说明(内置结构体)：
	func IsInteger： 如果元素是单个int则返回true。否则就代表是列表
	func GetInteger: 获取单个int值，如果是列表则返回nil
	func GetList: 获取列表，如果是单个整数则返回空列表，可直接修改其值
*/
func Constructor(nestedList []*NestedInteger) *NestedIterator {
	depthList := list.New()
	if len(nestedList) > 0 {
		depthList.PushBack(&nestedElement{nestedList: nestedList, index: 0})
	}
	return &NestedIterator{depthList: depthList}
}

/*
Next 获取下一个元素
*/
func (n *NestedIterator) Next() int {
	ne := n.depthList.Back().Value.(*nestedElement)
	nestedInteger := ne.nestedList[ne.index]
	ne.index++
	return nestedInteger.GetInteger()
}

/*
HasNext 判断是否有下一个
*/
func (n *NestedIterator) HasNext() bool {
	if n.depthList.Len() == 0 {
		return false
	}
	ne := n.depthList.Back().Value.(*nestedElement)
	if len(ne.nestedList) == ne.index { // 遍历完成后进行Pop操作
		n.depthList.Remove(n.depthList.Back())
		return n.HasNext()
	}
	nestedInteger := ne.nestedList[ne.index]
	if !nestedInteger.IsInteger() { // 处理列表
		ne.index++
		n.depthList.PushBack(&nestedElement{nestedList: nestedInteger.GetList(), index: 0})
		return n.HasNext()
	}
	return true
}

func main() {
	// [1,[2,21,[3]],2,3,[4,41]]
	param := []*NestedInteger{
		{t: true, i: 1},
		{t: false, list: []*NestedInteger{
			{true, 21, nil},
			{true, 22, nil}}},
		{true, 3, nil},
	}
	param = []*NestedInteger{
		{t: false, list: []*NestedInteger{}},
		//{true, 1, nil},
	}
	n := Constructor(param)
	for n.HasNext() {
		println(n.Next())
	}
}
